/*-------------------------------------------------------------------------
 *
 * integerset.c
 *	  数据结构有效地保存大集合的 64 位整数
 *
 * IntegerSet 提供了一种内存数据结构，用于保存一组任意的 64 位整数。内部，值存储在 B 树中，叶子级别使用 Simple-8b 算法进行特殊的打包表示，可以将附近值的簇非常紧凑地打包。
 *
 * 内存消耗取决于存储的值的数量，但也取决于值彼此之间的距离。在最佳情况下，随着长连续整数的运行，内存消耗可以低至每个整数 0.1 字节。在最坏情况下，如果整数相距超过 2^32，它使用大约每个整数 8 字节。在典型使用中，每个整数的消耗介于这两个极端之间，具体取决于存储的整数的范围，以及它们的“聚集程度”。
 *
 *
 * 接口
 * ---------
 *
 *	intset_create			- 创建一个新的空集合
 *	intset_add_member		- 向集合中添加一个整数
 *	intset_is_member		- 测试一个整数是否在集合中
 *	intset_begin_iterate	- 开始遍历集合中的所有整数
 *	intset_iterate_next		- 返回下一个集合成员（如果有）
 *
 * intset_create() 在当前内存上下文中创建集合。后续向数据结构中添加的操作将继续从该相同的上下文中分配，即使它不再是当前的。
 *
 * 请注意，没有函数可以释放整数集合。如果需要这样做，请创建一个专用的内存上下文来保存它，然后销毁该内存上下文。
 *
 *
 * 限制
 * -----------
 *
 * - 必须按顺序添加值。（随机插入将需要拆分节点，但尚未实现。）
 *
 * - 在迭代进行时无法添加值。
 *
 * - 不支持移除值。
 *
 * 这些限制都不是数据结构的基本限制，因此如果需要，可以通过编写一些新代码来解除这些限制。但当前使用该功能的用户并不需要它们。
 *
 *
 * 参考
 * ----------
 *
 * Simple-8b 编码基于：
 *
 * Vo Ngoc Anh, Alistair Moffat, 使用 64 位字的索引压缩，
 *   软件 - 实践与经验，第 40 卷第 2 期，第 131-147 页，2010 年 2 月
 *   (https://doi.org/10.1002/spe.948)
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/lib/integerset.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/htup_details.h"
#include "lib/integerset.h"
#include "port/pg_bitutils.h"
#include "utils/memutils.h"


/*
 * 单个 Simple-8b 码字中可以编码的最大整数数量。(在其他任何内容之前定义，以便我们可以使用它来调整数组大小。)
 */
#define SIMPLE8B_MAX_VALUES_PER_CODEWORD 240

/*
 * 内存中 B 树形状的参数。
 *
 * 这些设置每个内部节点和叶子节点的大小。它们不一定需要相同，因为树只是一个内存结构。
 * 默认的 64，每个节点大约占 1 KB。
 *
 * 如果更改这些，则必须重新计算 MAX_TREE_LEVELS！
 */
#define MAX_INTERNAL_ITEMS	64
#define MAX_LEAF_ITEMS	64

/*
 * 树的最大高度。
 *
 * MAX_TREE_ITEMS 是根据 B 树的“分叉”计算得出的。
 * 理论上，我们可以在一个集合中存储的最大项数是 2^64，
 * 因此 MAX_TREE_LEVELS 应设置为：
 *
 *   MAX_LEAF_ITEMS * MAX_INTERNAL_ITEMS ^ (MAX_TREE_LEVELS - 1) >= 2^64。
 *
 * 在实践中，我们需要的级别远少于此，因为你会在达到该数字之前就耗尽内存，但我们要保持保守。
 */
#define MAX_TREE_LEVELS		11

/*
 * 节点结构，用于内存中的 B 树。
 *
 * 内部节点持有指向叶子节点或下层内部节点的多个下行指针。
 * 对于每个下行指针，存储对应于下层节点的键值在一个排序数组中。
 * 存储的键值是低键。换句话说，如果下行指针的值为 X，则该子节点存储的所有项都 >= X。
 *
 * 每个叶子节点持有多个“项”，每个项中打包有不同数量的整数。
 * 每个项由两个 64 位字组成：第一个字存储项中第一个整数，采用明文格式。
 * 第二个字包含 0 到 240 个更多的整数，使用 Simple-8b 编码打包。
 * 通过以明文、未打包的格式存储第一个整数，我们可以使用二分搜索快速找到持有（或将持有）特定整数的项。
 * 并且通过以打包形式存储其余部分，如果有相似值的整数簇，我们仍然可以获得相当好的内存密度。
 *
 * 每个叶子节点还指向下一个叶子节点，从而可以轻松地从头到尾遍历叶子节点。
 */
typedef struct intset_node intset_node;
typedef struct intset_leaf_node intset_leaf_node;
typedef struct intset_internal_node intset_internal_node;

/* 叶子节点和内部节点的公共结构。 */
struct intset_node
{
	uint16		level;			/* 该节点的树层级 */
	uint16		num_items;		/* 该节点中的项数 */
};

/* 内部节点 */
struct intset_internal_node
{
	/* 公共头部，必须与 intset_node 匹配 */
	uint16		level;			/* 在内部节点上 >= 1 */
	uint16		num_items;

	/*
	 * 'values' 是键值的数组，'downlinks' 是指向下层节点的指针，
	 * 对应于键值。
	 */
	uint64		values[MAX_INTERNAL_ITEMS];
	intset_node *downlinks[MAX_INTERNAL_ITEMS];
};

/* 叶子节点 */
typedef struct
{
	uint64		first;			/* 此项中的第一个整数 */
	uint64		codeword;		/* 从 'first' 的 simple8b 编码差异 */
} leaf_item;

#define MAX_VALUES_PER_LEAF_ITEM	(1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)

struct intset_leaf_node
{
	/* 公共头部，必须与 intset_node 匹配 */
	uint16		level;			/* 在叶子上为 0 */
	uint16		num_items;

	intset_leaf_node *next;		/* 右侧兄弟，如果有的话 */

	leaf_item	items[MAX_LEAF_ITEMS];
};

/*
 * 我们在一个简单的数组中缓冲插入，然后将其打包并插入到 B-tree 中。 MAX_BUFFERED_VALUES 设置缓冲区的大小。 编码器假设它足够大，以便我们始终可以用缓冲的新项目填充叶子项。 换句话说，MAX_BUFFERED_VALUES 必须大于 MAX_VALUES_PER_LEAF_ITEM。 为了提高效率，请将其设置得更大。
 */
#define MAX_BUFFERED_VALUES			(MAX_VALUES_PER_LEAF_ITEM * 2)

/*
 * IntegerSet 是表示集合的顶级对象。
 *
 * 整数存储在一个内存中的 B-tree 结构中，以及一个用于新添加整数的数组。 IntegerSet 还跟踪关于内存使用的信息，以及在使用 intset_begin_iterate / intset_iterate_next 迭代集合时的当前位置。
 */
struct IntegerSet
{
	/*
	 * 'context' 是持有该整数集和所有树节点的内存上下文。
	 *
	 * 'mem_used' 跟踪使用的内存量。 我们在 integerset.c 中不对它做任何操作，但调用者可以通过 intset_memory_usage() 请求它。
	 */
	MemoryContext context;
	uint64		mem_used;

	uint64		num_entries;	/* 集合中的值的总数 */
	uint64		highest_value;	/* 存储在此集合中的最高值 */

	/*
	 * 用于存储打包值的 B-tree。
	 *
	 * 'rightmost_nodes' 持有指向每层右侧节点的指针。 rightmost_parent[0] 是右侧叶子，rightmost_parent[1] 是其父节点，以此类推，一直到根。这些在添加新值时是必需的。（目前，我们要求新值从末尾添加。）
	 */
	int			num_levels;		/* 树的高度 */
	intset_node *root;			/* 根节点 */
	intset_node *rightmost_nodes[MAX_TREE_LEVELS];
	intset_leaf_node *leftmost_leaf;	/* 最左边的叶子节点 */

	/*
	 * 尚未插入到树中的新项的保存区域。
	 */
	uint64		buffered_values[MAX_BUFFERED_VALUES];
	int			num_buffered_values;

	/*
	 * 迭代器支持。
	 *
	 * 'iter_values' 是一个准备返回给调用者的整数数组； 'iter_num_values' 是该数组的长度， 'iter_valueno' 是下一个索引。 'iter_node' 和 'iter_itemno' 指向叶子节点以及其中的项，以获取下一批值。
	 *
	 * 通常，'iter_values' 指向 'iter_values_buf'，该缓冲区包含从叶子项解码的项。但在我们扫描完整个 B-tree 后，我们也通过将 iter_values 指向 'buffered_values' 来迭代所有未缓冲的值。
	 */
	bool		iter_active;	/* 是否正在进行迭代？ */

	const uint64 *iter_values;
	int			iter_num_values;	/* 'iter_values' 中的元素数量 */
	int			iter_valueno;	/* 'iter_values' 的下一个索引 */

	intset_leaf_node *iter_node;	/* 当前叶子节点 */
	int			iter_itemno;	/* 'iter_node' 中要解码的下一个项 */

	uint64		iter_values_buf[MAX_VALUES_PER_LEAF_ITEM];
};

/*
 * 内部函数的原型。
 */
static void fc_intset_update_upper(IntegerSet *fc_intset, int fc_level,
								intset_node *fc_child, uint64 fc_child_key);
static void fc_intset_flush_buffered_values(IntegerSet *fc_intset);

static int	fc_intset_binsrch_uint64(uint64 fc_value, uint64 *fc_arr, int fc_arr_elems,
								  bool fc_nextkey);
static int	fc_intset_binsrch_leaf(uint64 fc_value, leaf_item *fc_arr, int fc_arr_elems,
								bool fc_nextkey);

static uint64 fc_simple8b_encode(const uint64 *fc_ints, int *fc_num_encoded, uint64 fc_base);
static int	fc_simple8b_decode(uint64 fc_codeword, uint64 *fc_decoded, uint64 fc_base);
static bool fc_simple8b_contains(uint64 fc_codeword, uint64 fc_key, uint64 fc_base);


/*
 * 创建一个新的、最初为空的整数集。
 *
 * 整数集是在当前内存上下文中创建的。 我们将所有后续分配也在同一上下文中进行，无论在向集合中添加新整数时当前的内存上下文是什么。
 */
IntegerSet *
intset_create(void)
{
	IntegerSet *fc_intset;

	fc_intset = (IntegerSet *) palloc(sizeof(IntegerSet));
	fc_intset->context = CurrentMemoryContext;
	fc_intset->mem_used = GetMemoryChunkSpace(fc_intset);

	fc_intset->num_entries = 0;
	fc_intset->highest_value = 0;

	fc_intset->num_levels = 0;
	fc_intset->root = NULL;
	memset(fc_intset->rightmost_nodes, 0, sizeof(fc_intset->rightmost_nodes));
	fc_intset->leftmost_leaf = NULL;

	fc_intset->num_buffered_values = 0;

	fc_intset->iter_active = false;
	fc_intset->iter_node = NULL;
	fc_intset->iter_itemno = 0;
	fc_intset->iter_valueno = 0;
	fc_intset->iter_num_values = 0;
	fc_intset->iter_values = NULL;

	return fc_intset;
}

/*
 * 分配一个新节点。
 */
static intset_internal_node *
fc_intset_new_internal_node(IntegerSet *fc_intset)
{
	intset_internal_node *fc_n;

	fc_n = (intset_internal_node *) MemoryContextAlloc(fc_intset->context,
													sizeof(intset_internal_node));
	fc_intset->mem_used += GetMemoryChunkSpace(fc_n);

	fc_n->level = 0;				/* 调用者必须设置 */
	fc_n->num_items = 0;

	return fc_n;
}

static intset_leaf_node *
fc_intset_new_leaf_node(IntegerSet *fc_intset)
{
	intset_leaf_node *fc_n;

	fc_n = (intset_leaf_node *) MemoryContextAlloc(fc_intset->context,
												sizeof(intset_leaf_node));
	fc_intset->mem_used += GetMemoryChunkSpace(fc_n);

	fc_n->level = 0;
	fc_n->num_items = 0;
	fc_n->next = NULL;

	return fc_n;
}

/*
 * 返回整数集中条目的数量。
 */
uint64 intset_num_entries(IntegerSet *fc_intset)
{
	return fc_intset->num_entries;
}

/*
 * 返回整数集使用的内存量。
 */
uint64 intset_memory_usage(IntegerSet *fc_intset)
{
	return fc_intset->mem_used;
}

/*
 * 添加一个值到集合中。
 *
 * 值必须按照顺序添加。
 */
void intset_add_member(IntegerSet *fc_intset, uint64 fc_x)
{
	if (fc_intset->iter_active)
		elog(ERROR, "cannot add new values to integer set while iteration is in progress");

	if (fc_x <= fc_intset->highest_value && fc_intset->num_entries > 0)
		elog(ERROR, "cannot add value to integer set out of order");

	if (fc_intset->num_buffered_values >= MAX_BUFFERED_VALUES)
	{
		/* 刷新我们的缓冲区的时间 */
		fc_intset_flush_buffered_values(fc_intset);
		Assert(fc_intset->num_buffered_values < MAX_BUFFERED_VALUES);
	}

	/* 将其添加到新添加值的缓冲区 */
	fc_intset->buffered_values[fc_intset->num_buffered_values] = fc_x;
	fc_intset->num_buffered_values++;
	fc_intset->num_entries++;
	fc_intset->highest_value = fc_x;
}

/*
 * 取一批缓冲的值，并将它们打包到B树中。
 */
static void fc_intset_flush_buffered_values(IntegerSet *fc_intset)
{
	uint64	   *fc_values = fc_intset->buffered_values;
	uint64		fc_num_values = fc_intset->num_buffered_values;
	int			fc_num_packed = 0;
	intset_leaf_node *fc_leaf;

	fc_leaf = (intset_leaf_node *) fc_intset->rightmost_nodes[0];

	/*
	 * 如果树是完全空的，创建第一个叶子页，它也是根节点。
	 */
	if (fc_leaf == NULL)
	{
		/*
		 * 这是集合中的第一项。
		 *
		 * 分配根节点。它也是一个叶子节点。
		 */
		fc_leaf = fc_intset_new_leaf_node(fc_intset);

		fc_intset->root = (intset_node *) fc_leaf;
		fc_intset->leftmost_leaf = fc_leaf;
		fc_intset->rightmost_nodes[0] = (intset_node *) fc_leaf;
		fc_intset->num_levels = 1;
	}

	/*
	 * 如果缓冲区中的值少于MAX_VALUES_PER_LEAF_ITEM，停止。
	 * 在大多数情况下，我们无法在单个值中编码那么多值，但这样，编码器不必担心输入耗尽。
	 */
	while (fc_num_values - fc_num_packed >= MAX_VALUES_PER_LEAF_ITEM)
	{
		leaf_item	fc_item;
		int			fc_num_encoded;

		/*
		 * 构造下一个叶子项，尽可能地打包尽可能多的缓冲值。
		 */
		fc_item.first = fc_values[fc_num_packed];
		fc_item.codeword = fc_simple8b_encode(&fc_values[fc_num_packed + 1],
										&fc_num_encoded,
										fc_item.first);

		/*
		 * 将项添加到节点，如果旧节点已满，则分配一个新节点。
		 */
		if (fc_leaf->num_items >= MAX_LEAF_ITEMS)
		{
			/* 分配新叶子并将其链接到树 */
			intset_leaf_node *fc_old_leaf = fc_leaf;

			fc_leaf = fc_intset_new_leaf_node(fc_intset);
			fc_old_leaf->next = fc_leaf;
			fc_intset->rightmost_nodes[0] = (intset_node *) fc_leaf;
			fc_intset_update_upper(fc_intset, 1, (intset_node *) fc_leaf, fc_item.first);
		}
		fc_leaf->items[fc_leaf->num_items++] = fc_item;

		fc_num_packed += 1 + fc_num_encoded;
	}

	/*
	 * 将任何剩余的缓冲值移动到数组的开头。
	 */
	if (fc_num_packed < fc_intset->num_buffered_values)
	{
		memmove(&fc_intset->buffered_values[0],
				&fc_intset->buffered_values[fc_num_packed],
				(fc_intset->num_buffered_values - fc_num_packed) * sizeof(uint64));
	}
	fc_intset->num_buffered_values -= fc_num_packed;
}

/*
 * 在创建新节点后，将下行链接插入父节点。
 *
 * 如果父节点也已满，则递归。
 */
static void fc_intset_update_upper(IntegerSet *fc_intset, int fc_level, intset_node *fc_child,
					uint64 fc_child_key)
{
	intset_internal_node *fc_parent;

	Assert(fc_level > 0);

	/*
	 * 如有必要，创建一个新的根节点。
	 */
	if (fc_level >= fc_intset->num_levels)
	{
		intset_node *fc_oldroot = fc_intset->root;
		uint64		fc_downlink_key;

		/* MAX_TREE_LEVELS应该绰绰有余，这种情况不应该发生 */
		if (fc_intset->num_levels == MAX_TREE_LEVELS)
			elog(ERROR, "could not expand integer set, maximum number of levels reached");
		fc_intset->num_levels++;

		/*
		 * 获取旧根页上的第一个值，用作下行链接。
		 */
		if (fc_intset->root->level == 0)
			fc_downlink_key = ((intset_leaf_node *) fc_oldroot)->items[0].first;
		else
			fc_downlink_key = ((intset_internal_node *) fc_oldroot)->values[0];

		fc_parent = fc_intset_new_internal_node(fc_intset);
		fc_parent->level = fc_level;
		fc_parent->values[0] = fc_downlink_key;
		fc_parent->downlinks[0] = fc_oldroot;
		fc_parent->num_items = 1;

		fc_intset->root = (intset_node *) fc_parent;
		fc_intset->rightmost_nodes[fc_level] = (intset_node *) fc_parent;
	}

	/*
	 * 将下行链接放置在父页面上。
	 */
	fc_parent = (intset_internal_node *) fc_intset->rightmost_nodes[fc_level];

	if (fc_parent->num_items < MAX_INTERNAL_ITEMS)
	{
		fc_parent->values[fc_parent->num_items] = fc_child_key;
		fc_parent->downlinks[fc_parent->num_items] = fc_child;
		fc_parent->num_items++;
	}
	else
	{
		/*
		 * 不合适。分配新父节点，将下行链接作为第一个项，并递归地将下行链接插入到新父节点的祖父节点。
		 */
		fc_parent = fc_intset_new_internal_node(fc_intset);
		fc_parent->level = fc_level;
		fc_parent->values[0] = fc_child_key;
		fc_parent->downlinks[0] = fc_child;
		fc_parent->num_items = 1;

		fc_intset->rightmost_nodes[fc_level] = (intset_node *) fc_parent;

		fc_intset_update_upper(fc_intset, fc_level + 1, (intset_node *) fc_parent, fc_child_key);
	}
}

/*
 * 集合中是否包含给定值？
 */
bool intset_is_member(IntegerSet *fc_intset, uint64 fc_x)
{
	intset_node *fc_node;
	intset_leaf_node *fc_leaf;
	int			fc_level;
	int			fc_itemno;
	leaf_item  *fc_item;

	/*
	 * 该值可能在新添加值的缓冲区中。
	 */
	if (fc_intset->num_buffered_values > 0 && fc_x >= fc_intset->buffered_values[0])
	{
		int			fc_itemno;

		fc_itemno = fc_intset_binsrch_uint64(fc_x,
									   fc_intset->buffered_values,
									   fc_intset->num_buffered_values,
									   false);
		if (fc_itemno >= fc_intset->num_buffered_values)
			return false;
		else
			return (fc_intset->buffered_values[fc_itemno] == fc_x);
	}

	/*
	 * 从根节点开始，沿B树向下遍历以找到正确的叶子节点。
	 */
	if (!fc_intset->root)
		return false;
	fc_node = fc_intset->root;
	for (fc_level = fc_intset->num_levels - 1; fc_level > 0; fc_level--)
	{
		intset_internal_node *fc_n = (intset_internal_node *) fc_node;

		Assert(fc_node->level == fc_level);

		fc_itemno = fc_intset_binsrch_uint64(fc_x, fc_n->values, fc_n->num_items, true);
		if (fc_itemno == 0)
			return false;
		fc_node = fc_n->downlinks[fc_itemno - 1];
	}
	Assert(fc_node->level == 0);
	fc_leaf = (intset_leaf_node *) fc_node;

	/*
	 * 二分查找以找到叶子页上的正确项
	 */
	fc_itemno = fc_intset_binsrch_leaf(fc_x, fc_leaf->items, fc_leaf->num_items, true);
	if (fc_itemno == 0)
		return false;
	fc_item = &fc_leaf->items[fc_itemno - 1];

	/* 这是与项上的第一个值匹配吗？ */
	if (fc_item->first == fc_x)
		return true;
	Assert(fc_x > fc_item->first);

	/* 它在打包的代码字中吗？ */
	if (fc_simple8b_contains(fc_item->codeword, fc_x, fc_item->first))
		return true;

	return false;
}

/*
 * 开始对所有值进行中序扫描。
 *
 * 在迭代进行时，您不能向集合中添加新值。
 */
void intset_begin_iterate(IntegerSet *fc_intset)
{
	/* 请注意，我们允许在中途放弃迭代 */
	fc_intset->iter_active = true;
	fc_intset->iter_node = fc_intset->leftmost_leaf;
	fc_intset->iter_itemno = 0;
	fc_intset->iter_valueno = 0;
	fc_intset->iter_num_values = 0;
	fc_intset->iter_values = fc_intset->iter_values_buf;
}

/*
 * 当迭代时返回下一个整数。
 *
 * 必须首先调用intset_begin_iterate()。intset_iterate_next()返回集合中的下一个值。如果有另一个值，则返回true，并将值存储在*next中。否则，返回false。
 */
bool intset_iterate_next(IntegerSet *fc_intset, uint64 *fc_next)
{
	Assert(fc_intset->iter_active);
	for (;;)
	{
		/* 如果有，返回下一个iter_values[]条目 */
		if (fc_intset->iter_valueno < fc_intset->iter_num_values)
		{
			*fc_next = fc_intset->iter_values[fc_intset->iter_valueno++];
			return true;
		}

		/* 解码当前叶节点中的下一个项，如果有的话 */
		if (fc_intset->iter_node &&
			fc_intset->iter_itemno < fc_intset->iter_node->num_items)
		{
			leaf_item  *fc_item;
			int			fc_num_decoded;

			fc_item = &fc_intset->iter_node->items[fc_intset->iter_itemno++];

			fc_intset->iter_values_buf[0] = fc_item->first;
			fc_num_decoded = fc_simple8b_decode(fc_item->codeword,
										  &fc_intset->iter_values_buf[1],
										  fc_item->first);
			fc_intset->iter_num_values = fc_num_decoded + 1;
			fc_intset->iter_valueno = 0;
			continue;
		}

		/* 该叶子上没有更多项，转到下一个节点 */
		if (fc_intset->iter_node)
		{
			fc_intset->iter_node = fc_intset->iter_node->next;
			fc_intset->iter_itemno = 0;
			continue;
		}

		/*
		 * 我们已经到达B树的末尾。但我们可能在新添加值的缓冲区中仍然有一些整数。
		 */
		if (fc_intset->iter_values == (const uint64 *) fc_intset->iter_values_buf)
		{
			fc_intset->iter_values = fc_intset->buffered_values;
			fc_intset->iter_num_values = fc_intset->num_buffered_values;
			fc_intset->iter_valueno = 0;
			continue;
		}

		break;
	}

	/* 没有更多结果。 */
	fc_intset->iter_active = false;
	*fc_next = 0;					/* 防止未初始化变量的警告 */
	return false;
}

/*
 * intset_binsrch_uint64() -- 搜索一个排序的 uint64 数组
 *
 * 返回第一个位置，其键小于或等于给定的键。
 * 返回的位置将是给定键的“插入”位置，
 * 也就是说，新的键应插入的位置。
 *
 * 'nextkey' 影响相等键的行为。如果为真，并且数组中存在
 * 一个相等的键，则返回的位置是相等键后面的直接位置。
 * 如果为假，则返回相等键本身的位置。
 */
static int fc_intset_binsrch_uint64(uint64 fc_item, uint64 *fc_arr, int fc_arr_elems, bool fc_nextkey)
{
	int			fc_low,
				fc_high,
				fc_mid;

	fc_low = 0;
	fc_high = fc_arr_elems;
	while (fc_high > fc_low)
	{
		fc_mid = fc_low + (fc_high - fc_low) / 2;

		if (fc_nextkey)
		{
			if (fc_item >= fc_arr[fc_mid])
				fc_low = fc_mid + 1;
			else
				fc_high = fc_mid;
		}
		else
		{
			if (fc_item > fc_arr[fc_mid])
				fc_low = fc_mid + 1;
			else
				fc_high = fc_mid;
		}
	}

	return fc_low;
}

/* 相同，但用于叶子项数组 */
static int fc_intset_binsrch_leaf(uint64 fc_item, leaf_item *fc_arr, int fc_arr_elems, bool fc_nextkey)
{
	int			fc_low,
				fc_high,
				fc_mid;

	fc_low = 0;
	fc_high = fc_arr_elems;
	while (fc_high > fc_low)
	{
		fc_mid = fc_low + (fc_high - fc_low) / 2;

		if (fc_nextkey)
		{
			if (fc_item >= fc_arr[fc_mid].first)
				fc_low = fc_mid + 1;
			else
				fc_high = fc_mid;
		}
		else
		{
			if (fc_item > fc_arr[fc_mid].first)
				fc_low = fc_mid + 1;
			else
				fc_high = fc_mid;
		}
	}

	return fc_low;
}

/*
 * Simple-8b 编码。
 *
 * Simple-8b 算法将 1 到 240 个整数打包到 64 位字中，
 * 称为“码字”。打包到单个码字中的整数数量取决于
 * 要打包的整数；小整数使用比大整数更少的位进行编码。
 * 例如，单个码字可以存储一个 60 位整数或两个 30 位整数。
 *
 * 由于我们存储的是唯一的、排序的整数集，实际上是编码
 * 连续整数之间的*差值*。这样，彼此接近的整数簇被高效地打包，
 * 而与它们的绝对值无关。
 *
 * 在 Simple-8b 中，每个码字由一个 4 位选择器组成，指示
 * 码字中编码了多少个整数，编码的整数被打包到剩余的 60 位中。
 * 选择器允许以 16 种不同方式使用剩余的 60 位，称为“模式”。
 * 每种模式中打包到单个码字中的整数数量在下面的 simple8b_modes
 * 表中列出。例如，考虑以下码字：
 *
 *      20 位整数       20 位整数       20 位整数
 * 1101 00000000000000010010 01111010000100100000 00000000000000010100
 * ^
 * 选择器
 *
 * 选择器 1101 在十进制中是 13。从下面的模式表中，我们看到
 * 它意味着码字编码了三个 20 位整数。在十进制中，
 * 这些整数是 18、500000 和 20。因为我们编码的是增量而不是
 * 绝对值，所以它们所代表的实际值是 18、500018 和
 * 500038。
 *
 * 模式 0 和 1 有点特殊；它们编码 240 或 120 个零
 * （这意味着 240 或 120 个连续整数，因为我们在编码整数
 * 之间的增量），而不使用码字的其余位。
 *
 * Simple-8b 不能编码大于 60 位的整数。大于
 * 这个值的数始终存储在叶子项的 'first' 字段中，而不在
 * 打包的码字中。如果存在一个整数序列，其差值超过
 * 2^60，码字将在这些项上不被使用。为了表示这一点，
 * 我们使用一个魔术 EMPTY_CODEWORD 码字值。
 */
static const struct simple8b_mode
{
	uint8		bits_per_int;
	uint8		num_ints;
}			simple8b_modes[17] =

{
	{0, 240},					/* 模式  0: 240 个零 */
	{0, 120},					/* 模式  1: 120 个零 */
	{1, 60},					/* 模式  2: 六十个 1 位整数 */
	{2, 30},					/* 模式  3: 三十个 2 位整数 */
	{3, 20},					/* 模式  4: 二十个 3 位整数 */
	{4, 15},					/* 模式  5: 十五个 4 位整数 */
	{5, 12},					/* 模式 6：十二个 5 位整数 */
	{6, 10},					/* 模式 7：十个 6 位整数 */
	{7, 8},						/* 模式 8：八个 7 位整数（浪费四位） */
	{8, 7},						/* 模式 9：七个 8 位整数（浪费四位） */
	{10, 6},					/* 模式 10：六个 10 位整数 */
	{12, 5},					/* 模式 11：五个 12 位整数 */
	{15, 4},					/* 模式 12：四个 15 位整数 */
	{20, 3},					/* 模式 13：三个 20 位整数 */
	{30, 2},					/* 模式 14：两个 30 位整数 */
	{60, 1},					/* 模式 15：一个 60 位整数 */

	{0, 0}						/* 哨兵值 */
};

/*
 * EMPTY_CODEWORD 是一个特殊值，用于表示“没有值”。
 * 如果下一个值太大而无法用 Simple-8b 编码，它将被使用。
 *
 * 这个值看起来像模式 0 的码字，但我们可以区分它，
 * 因为一个常规的模式 0 码字在未使用的位中会有零。
 */
#define EMPTY_CODEWORD		UINT64CONST(0x0FFFFFFFFFFFFFFF)

/*
 * 将多个整数编码为 Simple-8b 码字。
 *
 * （我们实际编码的是连续整数之间的增量。
 * “base”是 ints[0] 之前的值。）
 *
 * 输入数组必须至少包含 SIMPLE8B_MAX_VALUES_PER_CODEWORD
 * 个元素，确保我们可以生成一个完整的码字。
 *
 * 返回编码后的码字，并将 *num_encoded 设置为编码的输入
 * 整数的数量。如果第一个增量太大而无法编码，该值可以为零。
 */
static uint64 fc_simple8b_encode(const uint64 *fc_ints, int *fc_num_encoded, uint64 fc_base)
{
	int			fc_selector;
	int			fc_nints;
	int			fc_bits;
	uint64		fc_diff;
	uint64		fc_last_val;
	uint64		fc_codeword;
	int			fc_i;

	Assert(fc_ints[0] > fc_base);

	/*
	 * 选择用于该码字的“模式”。
	 *
	 * 在每次迭代中，检查下一个值是否可以在我们正在考虑的当前
	 * 模式中表示。如果太大，则升级到更宽的模式，并重复。
	 * 如果适合，则继续下一个整数。重复此过程，直到根据当前
	 * 模式码字满。
	 *
	 * 注意，我们没有任何方法表示码字中的未使用插槽，
	 * 因此我们要求每个码字必须“完整”。除非第一个增量太大
	 * 而无法编码，否则始终可以生成一个完整的码字。例如，如果
	 * 第一个增量很小但第二个太大而无法编码，我们将最终使用
	 * 最后一个“模式”，即 nints == 1。
	 */
	fc_selector = 0;
	fc_nints = simple8b_modes[0].num_ints;
	fc_bits = simple8b_modes[0].bits_per_int;
	fc_diff = fc_ints[0] - fc_base - 1;
	fc_last_val = fc_ints[0];
	fc_i = 0;						/* 我们接受的增量数量 */
	for (;;)
	{
		if (fc_diff >= (UINT64CONST(1) << fc_bits))
		{
			/* 太大，升级到下一个模式 */
			fc_selector++;
			fc_nints = simple8b_modes[fc_selector].num_ints;
			fc_bits = simple8b_modes[fc_selector].bits_per_int;
			/* 我们可能已经接受了足够的增量用于该模式 */
			if (fc_i >= fc_nints)
				break;
		}
		else
		{
			/* 接受这个增量；如果码字满则完成 */
			fc_i++;
			if (fc_i >= fc_nints)
				break;
			/* 检查下一个增量 */
			Assert(fc_ints[fc_i] > fc_last_val);
			fc_diff = fc_ints[fc_i] - fc_last_val - 1;
			fc_last_val = fc_ints[fc_i];
		}
	}

	if (fc_nints == 0)
	{
		/*
		 * 第一个增量太大而无法用 Simple-8b 编码。
		 *
		 * 如果输入中至少有一个不太大的整数，我们将使用模式 15
		 * （或更紧凑的模式）对其进行编码。因此，只有当第一个
		 * 增量 >= 2^60 时，我们才能到达这里。
		 */
		Assert(fc_i == 0);
		*fc_num_encoded = 0;
		return EMPTY_CODEWORD;
	}

	/*
	 * 使用选择的模式对整数进行编码。注意，我们将它们
	 * 反向顺序移入码字，以便在解码器中以正确的顺序输出。
	 */
	fc_codeword = 0;
	if (fc_bits > 0)
	{
		for (fc_i = fc_nints - 1; fc_i > 0; fc_i--)
		{
			fc_diff = fc_ints[fc_i] - fc_ints[fc_i - 1] - 1;
			fc_codeword |= fc_diff;
			fc_codeword <<= fc_bits;
		}
		fc_diff = fc_ints[0] - fc_base - 1;
		fc_codeword |= fc_diff;
	}

	/* 将选择器添加到码字，并返回 */
	fc_codeword |= (uint64) fc_selector << 60;

	*fc_num_encoded = fc_nints;
	return fc_codeword;
}

/*
 * 解码码字为整数数组。
 * 返回解码的整数数量。
 */
static int fc_simple8b_decode(uint64 fc_codeword, uint64 *fc_decoded, uint64 fc_base)
{
	int			fc_selector = (fc_codeword >> 60);
	int			fc_nints = simple8b_modes[fc_selector].num_ints;
	int			fc_bits = simple8b_modes[fc_selector].bits_per_int;
	uint64		fc_mask = (UINT64CONST(1) << fc_bits) - 1;
	uint64		fc_curr_value;

	if (fc_codeword == EMPTY_CODEWORD)
		return 0;

	fc_curr_value = fc_base;
	for (int fc_i = 0; fc_i < fc_nints; fc_i++)
	{
		uint64		fc_diff = fc_codeword & fc_mask;

		fc_curr_value += 1 + fc_diff;
		fc_decoded[fc_i] = fc_curr_value;
		fc_codeword >>= fc_bits;
	}
	return fc_nints;
}

/*
 * 这与simple8b_decode()非常相似，但不是将所有值解码到数组中，而是仅检查给定的“键”是否是码字的一部分。
 */
static bool fc_simple8b_contains(uint64 fc_codeword, uint64 fc_key, uint64 fc_base)
{
	int			fc_selector = (fc_codeword >> 60);
	int			fc_nints = simple8b_modes[fc_selector].num_ints;
	int			fc_bits = simple8b_modes[fc_selector].bits_per_int;

	if (fc_codeword == EMPTY_CODEWORD)
		return false;

	if (fc_bits == 0)
	{
		/* 0位情况的特殊处理。 */
		return (fc_key - fc_base) <= fc_nints;
	}
	else
	{
		uint64		fc_mask = (UINT64CONST(1) << fc_bits) - 1;
		uint64		fc_curr_value;

		fc_curr_value = fc_base;
		for (int fc_i = 0; fc_i < fc_nints; fc_i++)
		{
			uint64		fc_diff = fc_codeword & fc_mask;

			fc_curr_value += 1 + fc_diff;

			if (fc_curr_value >= fc_key)
			{
				if (fc_curr_value == fc_key)
					return true;
				else
					return false;
			}

			fc_codeword >>= fc_bits;
		}
	}
	return false;
}
